package practice12;

/**
 * # 问题描述
 *
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 * ## 输入格式
 *
 * 一个 `int` 型的数字，`0 <= num <= 2` 的 31 次方
 *
 * ## 输出格式
 *
 * 也是一个 `int` 型数字，代表字符串的总共可能性
 *
 * **输入样例**
 *
 * 输入: 12258
 *
 * **输出样例**
 *
 * 输出: 5
 *
 * 解释: 12258 有 5 种不同的翻译，分别是 "bccfi", "bwfi", "bczi", "mcfi" 和 "mzi"
 */
public class Main {
    public static int solution(int num) {
        String str = String.valueOf(num);
        int n = str.length();

        // dp[i] 表示从第 i 位开始的不同翻译方法数
        int[] dp = new int[n + 1];

        // 初始化最后一位和结束条件
        dp[n] = 1; // 空字符串有一种翻译方法
        dp[n - 1] = 1; // 最后一位单独翻译

        for (int i = n - 2; i >= 0; i--) {
            // 单独翻译当前位
            dp[i] = dp[i + 1];

            // 尝试将当前位与下一位组合起来翻译
            int twoDigits = Integer.parseInt(str.substring(i, i + 2));
            if (twoDigits >= 10 && twoDigits <= 25) {
                dp[i] += dp[i + 2];
            }
        }

        return dp[0];
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(12258) == 5); // true
        System.out.println(solution(1400112) == 6); // true
        System.out.println(solution(2110101) == 10); // true
    }
}